Use
the magic of counting sort: sort n
numbers in the range [0; 100000].
Input. First line contains number n (1 ≤ n ≤ 106). Then n
numbers are given that must be sorted.
Output. Print the sorted n numbers.
|
Sample input |
Sample output |
|
3 2 3 1 |
1 2 3 |
sorting
Input numbers
can be sorted using
counting sort, as
they are integers and we
know their range.
Input numbers store in array m.
#define MAX 100010
int
m[MAX];
Read the input data. In m[i] count the number of times the value i is encountered
among the given numbers.
scanf("%d",&n);
memset(m,0,sizeof(m));
for(i = 0; i < n; i++)
{
scanf("%d",&v);
m[v]++;
}
Print
the resulting array. Number
i must be printed m[i] times.
for(i = 0; i < MAX; i++)
for(j = 0; j
< m[i]; j++)
printf("%d
",i);
printf("\n");
#include <cstdio>
#include <vector>
using namespace std;
vector<int> v;
int
n, i;
vector<int> sort(vector<int>
&a)
{
int i, len =
a.size();
vector<int>
c(100001), b(len);
for(i = 0; i
< len; i++) c[a[i]]++;
for(i = 1; i
< 100001; i++) c[i] += c[i-1];
for(i = 0; i
< len; i++)
b[--c[a[i]]] = a[i];
return b;
}
int
main(void)
{
scanf("%d",&n);
v.resize(n);
for(i = 0; i
< n; i++)
scanf("%d",&v[i]);
v = sort(v);
for(i = 0; i
< v.size(); i++)
printf("%d
",v[i]);
printf("\n");
return 0;
}
Java realization
import java.util.*;
public class Main
{
static int MAX = 100001;
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m[] = new int[MAX];
for(int i = 0; i < n; i++)
{
int v = con.nextInt();
m[v]++;
}
for(int i = 0; i < MAX; i++)
for(int j = 0; j < m[i]; j++)
System.out.print(i + " ");
System.out.println();
con.close();
}
}